If you have technical difficulties (apart from answering the questions themselves), request assistance.

QUESTION 1: General Concurrency [14 marks]

1. In the context of concurrent programming with two or more threads performing unsynchronized access to shared variables or objects may experience interference from each other. Briefly explain the term interference and illustrate this with a simple example written in pseudo code.
   Enter your answer in the file Q1/Q1.txt.
   [4 marks]

2. Define the term semaphore. Does the implementation of a semaphore require special hardware support or can a semaphore be implemented in any high-level programming language? Give precise reasons.
   Enter your answer in the file Q1/Q1.txt.
   [4 marks]

3. Describe the term buffer, in the context of concurrent and distributed systems. Describe a scenario or mode of communication where buffers play an important role.
   Enter your answer in the file Q1/Q1.txt.
   [4 marks]

4. It is possible to perform condition synchronization between a server (or monitor) and its clients as follows: the client repeatedly makes requests to the server and receives a response, until the response indicates that the request has been successfully performed (a positive response will only occur when the associated condition for the request is satisfied). State two disadvantages over the traditional approach to performing condition synchronization, i.e. the client makes a single request and waits (e.g. through a Java wait() call) for a response (which indicates the request has been performed).
   Enter your answer in the file Q1/Q1.txt.
   [2 marks]

QUESTION 2: Mutual Exclusion and Synchronization [24 marks]

1. A museum allows visitors to enter through the east entrance and leave through the west. At most N visitors may be in the museum at any time. When the museum opens, the janitor signals to a controller to accept both enter and leave actions; when the museum closes, only visitors already inside the museum may leave.

   Implement this system as a concurrent program with threads using shared objects in the programming language of your choice. Separate threads must be used to model the east door (generating enter actions), the west door (generating leave actions), and the janitor (generating sequences of open and close actions). A shared object, preferably in the form of a monitor, may be used to implement the controller.
   Enter your program in the sub-directory Q2/Q2p1. If programming in Java, use the provided Museum.java as a template. If using another language, prefix your main program file with the name museum, and your solution should produce the same output and have the equivalent sleep behavior as for Museum.java.
   [12 marks]

2. In the implementation of a monitor (and its interface to client threads or processes), three distinct functions are performed (performing mutual exclusion is considered not to be one of these). Name these three functions. State which are the same and which are different if the monitor is implemented using the threaded (shared object) paradigm, compared to the message passing paradigm.
   Enter your answer in the file Q2/Q2.txt.
   [4 marks]

3. Consider an implementation of a Bakery simulation, as defined in the assignments for this course. Assume that the implementation consists of active threads or processes representing the customers and a monitor representing the bakery state (including the servers). What defensive programming techniques should be used in such a system?
   Enter your answer in the file Q2/Q2.txt.
   [6 marks]

4. Consider the trace in the file bakeryTrace.txt, generated from a Bakery simulation, as defined in the assignments for this course. What deficiency does it have? Is this considered a deficiency in safety or liveness?
   Enter your answer in the file Q2/Q2.txt.
   [2 marks]

QUESTION 3: Safety and Liveness [15 marks]

while (1) { // thread 0
   // non-critical section 0
   ...
   while (inCS1==1) {/*spin*/}
   inCS0 = 1;
   // critical section 0
   ...
   inCS0 = 0;
}

while (1) { // thread 1
   // non-critical section 1
   ...
   while (inCS0==1) {/*spin*/}
   inCS1 = 1;
   // critical section 1
   ...
   inCS1 = 0;
}

1. Model the algorithm in FSP, capturing the essential characteristics for mutual exclusion.
   Place your answer in the file Q3/mutex.lts.
   [5 marks]

   Hint: an FSP process will model each thread. For each thread, model the execution of critical regions by the sequence crit.enter and crit.exit; that of the non-critical section as simply noncrit. The variables can be modelled as inCS0:VAR and inCS1:VAR, where

   set VarAlpha = {read[0..1], write[0..1]}
   VAR = VAR[0],
   VAR[i:0..1] = ( read[i] -> VAR[i]
                 | write[j:0..1] -> VAR[j] ).
   

   Note also that the alphabets of the processes for each thread should be extended by inCS0, inCS1}.VarAlpha before being composed into the final system.

2. Does the algorithm ensure mutual exclusion? If so, briefly explain why. If not, state a sequence of actions (preferably in the form of a trace, the shorter the better) which shows how it is violated.
   Place your answer in the file Q3/Q3.txt.
   [2 marks]

3. Specify an FSP safety property and a composition using this property which could be used to formally check whether mutual exclusion is in fact preserved.
   Place your answer in the file Q3/mutex.lts.
   [2 marks]

4. Can the algorithm deadlock? Briefly explain why or why not.
   Place your answer in the file Q3/Q3.txt.
   [3 marks]

5. COMP6310 students, answer the following: Specify FSP progress property(ies) which states that, once a thread is waiting to enter its critical region, it will eventually be allowed to enter.
   Place your answer in the file Q3/mutex.lts.
   Briefly explain whether you expect it to be violated, i.e. whether starvation is possible.
   Place your answer in the file Q3/Q3.txt.

   COMP2310 students only: Briefly explain whether you expect the algorithm has the property that, once a thread is waiting to enter its critical region, it will (always) eventually be allowed to enter.
   Place your answer in the file Q3/Q3.txt.

   
   [3 marks]

QUESTION 4: Message Passing [14 marks]

BUFFER(N=5) = COUNT[0],
COUNT[ct:0..N] = ( when (ct < N) put -> COUNT[ct+1]
                 | when (ct > 0) get -> COUNT[ct-1]).
PRODUCER = ( put -> PRODUCER ).
CONSUMER = ( get -> CONSUMER ).
||BOUNDEDBUFFER = (PRODUCER || BUFFER(5) || CONSUMER).

public class Selectable {
    public void guard(boolean g);
}
public class Channel<T> extends Selectable {
    public synchronized void send(T v); 
    public synchronized T receive();
}
public class Select {
    public void add(Selectable s); 
    public synchronized int choose();
}

Place your answer in the directory Q4. If programming in Java, use the provided Q4/BoundedBuffer.java as a template. If using another language, prefix your main program file with the name boundedbuffer, and your solution should produce the same output and have the equivalent sleep behavior as for BoundedBuffer.java.
[14 marks]

QUESTION 5: Architectures [20 marks]

1. Three programming languages for concurrency are Ada95, Java and C/Posix. Briefly describe the characteristics of each in terms of level of abstraction, support for consistency (conversely the susceptibility to errors) and efficiency. Illustrate this on a specific simple example such as a bounded buffer implementation.
   Place your answer in the file Q5/Q5.txt.

   
   [6 marks]

2. Write a (C) program to implement the compound shell command
   ls | wc -w
   by using the fork() system call and each process executing one of the sub-commands. It may be assumed that the ls and wc executables are in the /bin and /usr/bin directories, respectively.
   Place your answer in the directory Q5/Q5p2. If programming in C, use the provided Q5/p2/combcmd.c as a template. If using another language, prefix your main program file with the name combcmd.
   [7 marks]

   Hint: you may find the execl(), pipe() and dup2() system calls useful.

3. State two limitations of Posix pipes as a form of inter-process communication.
   Place your answer in the file Q5/Q5.txt.

   
   [2 marks]

4. Consider a user wishing to connect via the Secure Shell remote login client ssh to a remote server at IP address 150.203.24.2. The remote server has a Secure Shell daemon process (sshd) listening on port 22. Describe the series of socket system calls that both (i) the ssh process on the local host and (ii) the sshd on the remote host must perform in order to establish a connection.
   Place your answer in the file Q5/Q5.txt.
   [5 marks]

   Hint: your answer is likely to include the system calls socket(), connect(), bind(), listen() and accept().

QUESTION 6: Distributed Systems [13 marks]

1. The User Datagram Protocol (UDP) is an unreliable protocol, whereas the Transport Control Protocol (TCP) is deemed reliable. Why is UDP useful? Give an example in distributed systems where the UDP is preferred over TCP.
   Place your answer in the file Q6/Q6.txt.
   [2 marks]

2. The following diagram shows a system of three processes using Lamport's algorithm for logical time. The initial value of the logical time in each process is shown in the first box in each line. Timing events are indicated by subsequent boxes; these may or may not be associated with message passing (indicated by arrows).

   
   Enter the value of the logical clock which should appear in each of the labelled square boxes. Place your answer in the file Q6/Q6.txt.
   [3 marks]

3. Consider a system using transactions with two-phase locking. Explain why using reader/writers locks is useful, and discuss whether, for a typical scenario, different priorities should be given to readers or writers.
   Place your answer in the file Q6/Q6.txt.
   [2 marks]

4. Explain why a multicast over a group of processes is important in the context of distributed systems
   Place your answer in the file Q6/Q6.txt.
   [2 marks]

5. State the CAP Theorum as it applies to distributed systems. Describe a scenario where it might be preferable to sacrifice the `C' aspect of the theorum in favor of the `A' and `P' aspects.
   Place your answer in the file Q6/Q6.txt.
   [4 marks]